home *** CD-ROM | disk | FTP | other *** search
/ The PC-SIG Library 9 / The PC-SIG Library on CD ROM - Ninth Edition.iso / 401_500 / DISK0420 / DISK0420.ZIP / FCOMPARE.C < prev    next >
Text File  |  1985-05-02  |  13KB  |  415 lines
  1. /**********************************************************************
  2.  
  3. Copyright (c) 1985, Charles Daney
  4. All Rights Reserved
  5.  
  6. The FCOMPARE program implements Paul Heckel's algorithm from the
  7. Communications of the ACM, April 1978, for detecting the differences
  8. between two files. This algorithm has the advantage over more commonly
  9. used compare algorithms that it is fast and can detect differences of an
  10. arbitrary number of lines.
  11.  
  12. A full statement of terms of use and disclaimer of warranty appears at
  13. the end of this file.
  14.  
  15. The source code has been written for the CI C86 compiler. It uses
  16. declarations of 'unsigned long' and 'unsigned char', so a prerequisite
  17. to using any other compiler is support for these types.
  18.  
  19. Modification history.
  20.  
  21. Author          Date        Purpose
  22. Charles Daney   4/10/85     original release
  23.  
  24. Author's address:
  25.  
  26. Charles Daney
  27. Quercus Systems
  28. 19567 Dorchester Drive
  29. Saratoga, CA 95070
  30. (408) 257-8440
  31.  
  32. **********************************************************************/
  33.  
  34. #include "stdio.h"
  35. #define MAXLINES 5000
  36. #define FULL 0x80
  37. #define TABS 0x40
  38. #define TRIM 0x20
  39. #define ON 1
  40. #define OFF 0
  41.  
  42. long hash1[MAXLINES], hash2[MAXLINES];
  43. unsigned char occ1[8192], occ2[8192];
  44. int n1, n2;
  45. FILE *file1, *file2;
  46. unsigned char flag1;
  47.  
  48. struct {
  49.      char *optname;
  50.      char min;
  51.      char *flag;
  52.      unsigned char bit;
  53.      unsigned char onoff; } optable[] = {
  54.           { "FULL", 1, &flag1, FULL, ON },
  55.           { "BRIEF", 1, &flag1, FULL, OFF },
  56.           { "TABS", 1, &flag1, TABS, ON },
  57.           { "NOTABS", 3, &flag1, TABS, OFF },
  58.           { "TRIM", 2, &flag1, TRIM, ON },
  59.           { "NOTRIM", 4, &flag1, TRIM, OFF },
  60.           { 0, 0, 0, 0, 0 } };
  61.  
  62. /* main program */
  63. main(argc,argv)
  64. int argc;
  65. char *argv[];
  66. {
  67.      int i, j, k;
  68.      unsigned char linked;
  69.  
  70.      puts("V1.1 Copyright (c) 1985, Charles Daney\n");
  71.      flag1 = 0;
  72.      if (argc<3) {
  73.           printf("Format is: FCOMPARE filespec1 filespec2 [options]\n");
  74.           printf("  options:\n");
  75.           printf("     Full - show full lines.\n");
  76.           printf("     Brief - show first 34 characters of lines.\n");
  77.           printf("     Tabs - expand tabs before comparing.\n");
  78.           printf("     NOTabs - don't expand tabs.\n");
  79.           printf("     TRim - ignore trailing blanks.\n");
  80.           printf("     NOTRim - don't ignore trailing blanks.\n");
  81.           return;
  82.           }
  83.  
  84. /* examine possible options */
  85.      for (i=3; i<argc; i++) {
  86.           for (j=0; optable[j].optname; j++) {
  87.                if (match(argv[i],optable[j].optname,optable[j].min)) {
  88.                     if (optable[j].onoff==ON)
  89.                          *optable[j].flag |= optable[j].bit;
  90.                          else *optable[j].flag &= ~optable[j].bit;
  91.                     break;
  92.                     }
  93.                }
  94.           if (optable[j].optname==0) {
  95.                printf("Invalid parameter: '%s'.\n",argv[i]);
  96.                return;
  97.                }
  98.           }
  99.      file1 = fopen(argv[1],"r");
  100.      if (file1==0) {
  101.           printf("Unable to open file '%s'.\n",argv[1]);
  102.           return;
  103.           }
  104.      file2 = fopen(argv[2],"r");
  105.      if (file2==0) {
  106.           printf("Unable to open file '%s'.\n",argv[2]);
  107.           return;
  108.           }
  109.  
  110. /* step 1: read first file and hash it */
  111.      printf("Reading file '%s'.\n",argv[1]);
  112.      n1 = input(file1,hash1,occ1);
  113.      fseek(file1,0L,0);
  114.  
  115. /* step 2: read second file and hash it */
  116.      printf("Reading file '%s'.\n",argv[2]);
  117.      n2 = input(file2,hash2,occ2);
  118.      fseek(file2,0L,0);
  119.  
  120. /* step 3: identify lines that are unique in both files */
  121.      for (i=0; i<8192; i++) occ1[i] &= occ2[i];
  122.  
  123. /* step 4: link together matching unique lines */
  124.      for (i=0; i<n1; i++) {
  125.           if (getbits(occ1,-hash1[i])!=1) continue;
  126.           for (j=0; i+j<n2 || i-j>=0; j++) {
  127.                if (i+j<n2) if (hash2[i+j]==hash1[i]) {
  128.                     hash1[i] = i+j;
  129.                     hash2[i+j] = i;
  130.                     break;
  131.                     }
  132.                if (i-j>=0) if (hash2[i-j]==hash1[i]) {
  133.                     hash1[i] = i-j;
  134.                     hash2[i-j] = i;
  135.                     break;
  136.                     }
  137.                }
  138.           }
  139.  
  140. /* step 5: link the first and last lines, if possible */
  141.      if (hash1[0]<0 && hash1[0]==hash2[0]) hash1[0] = hash2[0] = 0;
  142.      if (hash1[n1-1]<0 && hash1[n1-1]==hash2[n2-1]) {
  143.           hash1[n1-1] = n2-1;
  144.           hash2[n2-1] = n1-1;
  145.           }
  146.  
  147. /* step 6: starting from linked lines, link following lines that match */
  148.      linked = 0;
  149.      for (i=0; i<n1; i++) {
  150.           if (hash1[i]>=0) linked = 1;
  151.           else if (linked==1) {
  152.                if (hash1[i]==hash2[hash1[i-1]+1]) {
  153.                     hash1[i] = hash1[i-1]+1;
  154.                     hash2[hash1[i]] = i;
  155.                     }
  156.                else linked = 0;
  157.                }
  158.           }
  159.  
  160. /* step 7: link matching lines that precede linked lines */
  161.      linked = 0;
  162.      for (i=n1-1; i>=0; i--) {
  163.           if (hash1[i]>=0) linked = 1;
  164.           else if (linked==1) {
  165.                if (hash1[i]==hash2[hash1[i+1]-1]) {
  166.                     hash1[i] = hash1[i+1] - 1;
  167.                     hash2[hash1[i]] = i;
  168.                     }
  169.                else linked = 0;
  170.                }
  171.           }
  172. /* for (i=0; i<n1 || i<n2; i++) printf("%12ld %12ld\n",hash1[i],hash2[i]);*/
  173.  
  174. /* step 8: display the results */
  175.      for (i=j=0; i<n1 && j<n2;) {
  176.           if (hash1[i]<j && hash2[j]<i) {
  177.                output(i++,j++);
  178.                continue;
  179.                }
  180.           if (hash1[i]<j) {
  181.                output(i++,-1);
  182.                continue;
  183.                }
  184.           if (hash2[j]<i) {
  185.                output(-1,j++);
  186.                continue;
  187.                }
  188.           if (hash1[i]==j) {
  189.                for (k=1; i+k<=n1 && j+k<=n2 && hash1[i+k]==j+k; k++);
  190.                printf("\n*** %d line(s) match. ***\n\n",k);
  191.                i += k;
  192.                j += k;
  193.                continue;
  194.                }
  195.           if (hash1[i]-j <= hash2[j]-i) {
  196.                for (k=j; k<hash1[i]; k++) output(-1,k);
  197.                j = hash1[i];
  198.                continue;
  199.                }
  200.           else {
  201.                for (k=i; k<hash2[j]; k++) output(k,-1);
  202.                i = hash2[j];
  203.                continue;
  204.                }
  205.           }
  206.      if (i<n1) for (k=i; k<n1; k++) output(k,-1);
  207.      if (j<n2) for (k=j; k<n2; k++) output(-1,k);
  208.      fclose(file1);
  209.      fclose(file2);
  210.      }
  211.  
  212. /* read in file, build hash & occurrence tables */
  213. input(file,hashvect,occ)
  214. int file;
  215. long hashvect[];
  216. unsigned char occ[];
  217. {
  218.      int i, j;
  219.      long h;
  220.      unsigned char bits, buffer[256], temp[256];
  221.      long hash();
  222.  
  223.      for (i=0; i<MAXLINES; i++) {
  224.           if ((flag1&TABS)==0) {
  225.                if (fgets(buffer,256,file)==0) return(i);
  226.                }
  227.           else {
  228.                if (fgets(temp,256,file)==0) return(i);
  229.                tabex(temp,buffer);
  230.                }
  231.           if (flag1&TRIM) {
  232.                for (j=0; j<256 && j>=0 && buffer[j] && buffer[j]!='\n'; j++);
  233.                for (j=j-1; j>=0 && buffer[j]==' ' ; j--);
  234.                buffer[j+1] = 0;
  235.                }
  236.           h = hash(buffer);
  237.           if (h<0) hashvect[i] = h; else hashvect[i] = -h;
  238.           bits = getbits(occ,-hashvect[i]);
  239.           if (bits==0) setbits(occ,-hashvect[i],1);
  240.           else if (bits==1) setbits(occ,-hashvect[i],2);
  241.           }
  242.      printf("File truncated at %d lines.\n",MAXLINES);
  243.      return(i-1);
  244.      }
  245.  
  246. /* hash a character string */
  247. long hash(s)
  248. unsigned char *s;
  249. {
  250.      long h=0, h1;
  251.      while (*s) {
  252.           h1 = h;
  253.           h = h<<1;
  254.           if (h1<0) h |= 1;
  255.           h ^= *s++;
  256.           }
  257.      if (h==0) h = 1;
  258.      return(h);
  259.      }
  260.  
  261. /* extract bits from the occurrence vector */
  262. getbits(array,indx)
  263. unsigned char *array;
  264. unsigned long indx;
  265. {
  266.      unsigned i, j;
  267.      indx &= 32767;
  268.      i = indx>>2;
  269.      j = indx - (i<<2);
  270.      return(array[i]>>((3-j)<<1) & 0x03);
  271.      }
  272.  
  273. /* store bits in the occurrence array */
  274. setbits(array,indx,x)
  275. unsigned char *array;
  276. unsigned long indx;
  277. unsigned char x;
  278. {
  279.      unsigned i, j, shift;
  280.  
  281.      indx &= 32767;
  282.      i = indx>>2;
  283.      j = indx - (i<<2);
  284.      shift = (3-j)<<1;
  285.      array[i] &= ~(0x03<<shift);
  286.      array[i] |= x<<shift;
  287.      }
  288.  
  289. /* display the results of comparison */
  290. output(l1,l2)
  291. int l1, l2;
  292. {
  293.      static int cl1 = 0, cl2 = 0;
  294.      char line[81];
  295.      unsigned int bi1=0, bi2=0;
  296.      unsigned char end1=1, end2=1;
  297.      int i;
  298.      char buffer1[256], buffer2[256], temp[256];
  299.  
  300.      for (i=0; i<80; i++) line[i] = ' ';
  301.      line[80] = 0;
  302.      if (l1>=0) {
  303.           for (i=cl1; i<=l1; i++)
  304.                if((flag1&TABS)==0) fgets(buffer1,256,file1);
  305.                else {
  306.                     fgets(temp,256,file1);
  307.                     tabex(temp,buffer1);
  308.                     }
  309.           cl1 = l1 + 1;
  310.           sprintf(line,"%4d ",l1+1);
  311.           line[5] = ' ';
  312.           for (i=0; buffer1[i+bi1] && buffer1[i+bi1]!='\n' && i<34; i++)
  313.                line[i+5] = buffer1[i+bi1];
  314.           if (i==34) {
  315.                bi1 += 34;
  316.                end1 = 0;
  317.                }
  318.           }
  319.      if (l2>=0) {
  320.           for (i=cl2; i<=l2; i++)
  321.                if((flag1&TABS)==0) fgets(buffer2,256,file2);
  322.                else {
  323.                     fgets(temp,256,file2);
  324.                     tabex(temp,buffer2);
  325.                     }
  326.           cl2 = l2 + 1;
  327.           sprintf(line+40,"%4d ",l2+1);
  328.           line[45] = ' ';
  329.           for (i=0; buffer2[i+bi2] && buffer2[i+bi2]!='\n' && i<34; i++)
  330.                line[i+45] = buffer2[i+bi2];
  331.           if (i==34) {
  332.                bi2 += 34;
  333.                end2 = 0;
  334.                }
  335.           }
  336.      line[45+i] = '\n';
  337.      line[46+i] = 0;
  338.      fwrite(line,1,46+i,stdout);
  339.      if (flag1 & FULL) while (!end1 || !end2) {
  340.           for (i=0; i<80; i++) line[i] = ' ';
  341.           if (!end1) {
  342.                for (i=0; buffer1[i+bi1] && buffer1[i+bi1]!='\n' && i<34; i++)
  343.                     line[i+5] = buffer1[i+bi1];
  344.                if (i==34) bi1 += 34; else end1 = 1;
  345.                }
  346.           if (!end2) {
  347.                for (i=0; buffer2[i+bi2] && buffer2[i+bi2]!='\n' && i<34; i++)
  348.                     line[i+45] = buffer2[i+bi2];
  349.                if (i==34) bi2 += 34; else end2 = 1;
  350.                }
  351.           line[45+i] = '\n';
  352.           line[46+i] = 0;
  353.           fwrite(line,1,46+i,stdout);
  354.           }
  355.      }
  356.  
  357. /* match strings with specified minimum */
  358. match(s1,s2,min)
  359. unsigned char *s1, *s2, min;
  360. {
  361.      unsigned int i;
  362.      for (i=0; *s1 && *s2; i++) if (toupper(*s1++) != *s2++) return(0);
  363.      if (*s1==0) return(i>=min);
  364.      return(0);
  365.      }
  366.  
  367. /* expand tabs */
  368. tabex(s1,s2)
  369. unsigned char *s1, *s2;
  370. {
  371.      int i;
  372.      unsigned char j;
  373.  
  374.      for (i=j=0; s1[i]; i++) {
  375.           if (s1[i] != 0x09) {
  376.                s2[j++] = s1[i];
  377.                continue;
  378.                }
  379.           do s2[j++] = ' '; while(j%8 != 0);
  380.           }
  381.      s2[j] = 0;
  382.      }
  383.  
  384. /**********************************************************************
  385.  
  386. Permission is granted to freely distribute this code, but not for
  387. profit, provided that this notice and the following disclaimer are
  388. included in their entirety and without modifications of any sort. This
  389. work may not be sold (except for a nominal media charge), or included
  390. in any other work to be sold, without the written permission of the
  391. author.
  392.  
  393. If you modify this code, please include your name and a description of
  394. the modification in the change history at the top of this file.
  395. Modifications should be clearly indicated as to location and purpose,
  396. with descriptive comments that clearly identify altered lines. The
  397. author would appreciate hearing of any modifications that may be made.
  398.  
  399. Disclaimer:
  400.  
  401. This program is provided "as-is" without warranty of any kind, either
  402. expressed or implied, including, but not limited to the implied
  403. warranties of merchantability and fitness for a particular purpose. The
  404. entire risk as to the results and performance of the program is assumed
  405. by the user. Should the program prove defective, you (and not the
  406. author) assume the entire cost of all necessary servicing, repair, or
  407. correction.
  408.  
  409. Neither the author nor anyone else who has been involved in the
  410. creation, production or delivery of this program shall be liable for any
  411. direct, indirect, consequential or incidental damages arising out of the
  412. use or inability to use this program.
  413.  
  414. **********************************************************************/
  415.